package com.gong.suanfa.lianxi;

import java.util.*;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/11 0011 9:36
 */


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    public static void main(String[] args) {
        char[][] chars = {{'1','1','1'},{'0','1','0'},{'1','1','1'}};

        int i = numIslands(chars);

        System.out.println(i);
    }

    public static int numIslands(char[][] grid) {
        if (grid == null){
            return 0;
        }
        int m = grid.length; //行数
        int n = grid[0].length;//列数
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    res++;
                    int[] ints = setFound(grid, i, j);//将其相连的岛屿设为0
                    i = ints[0];j=ints[1];
                }
            }
        }

        return res;

    }


    private static int[] setFound(char[][] grid, int i, int j) {
        Queue<Integer> hang = new LinkedList();
        Queue<Integer> lie = new LinkedList();
        hang.add(i);lie.add(j);
        int[] ints = new int[2];

        while (hang.size()!=0){
            int m = hang.poll();
            int n = lie.poll();

            if (grid[m][n] == '1'){
                grid[m][n] = '0';
            }
            if (m+1<grid.length && grid[m+1][n] == '1'){//下
                hang.add(m+1);lie.add(n);
            }
            if (n+1< grid[0].length && grid[m][n+1] == '1'){//右
                hang.add(m);lie.add(n+1);
            }
            if (m-1 >= 0 && grid[m-1][n] == '1'){//上
                hang.add(m-1);lie.add(n);
            }
            if (n-1 >= 0 && grid[m][n-1] == '1'){//左
                hang.add(m);lie.add(n-1);
            }
            ints[0] = m;
            ints[1] = n;
        }
        return ints;
    }

}
